package algorithm.状态压缩的动态规划;

/*
铺砖问题
你有无限的1*2的砖块，要铺满N*M的区域，
不同的铺法有多少种?
* */
public class PavingTile {

    public static int way(int N, int M){
        int status = 0;
        int[][] dp =new int[1 << M][N];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process(status, 0, N, M, dp);
    }

    public static int process(int status, int row, int N, int M, int[][] dp){
        if(row == N - 1){
            if(status == (1 << M) - 1)
                return 1;
            int num = 0;
            for (int i = 0; i < M; i++) {
                if((status & (1 << i)) != 0 && num % 2 != 0)
                    return 0;
                else
                    if((status & (1 << i)) != 0)
                        num = 0;

                if((status & (1 << i)) == 0)
                    num++;
            }
            if(num % 2 != 0)
                return 0;

            return 1;
        }

        if(dp[status][row] != -1)
            return dp[status][row];

        return dfs(status, M - 1, row, N, M, 0,dp);
    }

    public static int dfs(int status, int column, int row, int N, int M, int nextStatus, int[][] dp){
        if(status == (1 << M) - 1){
            int num = process(nextStatus, row + 1, N, M, dp);
            dp[nextStatus][row + 1] = num;
            return num;
        }

        while((status & (1 << column)) != 0)
            column--;

        int num1 = dfs(status | (1 << column), column - 1, row, N, M, nextStatus | (1 << column), dp);

        int num2 = 0;
        if(column >= 1 && (status & (1 << (column - 1))) == 0){
            num2 = dfs(status | (1 << column) | (1 << (column - 1)), column - 2, row, N, M, nextStatus, dp);
        }

        return num1 + num2;

    }

    public static int ways4(int N, int M) {
        if (N < 1 || M < 1 || ((N * M) & 1) != 0) {
            return 0;
        }
        if (N == 1 || M == 1) {
            return 1;
        }
        int big = N > M ? N : M;
        int small = big == N ? M : N;
        int sn = 1 << small;
        int limit = sn - 1;
        int[] dp = new int[sn];
        dp[limit] = 1;
        int[] cur = new int[sn];
        for (int level = 0; level < big; level++) {
            for (int status = 0; status < sn; status++) {
                if (dp[status] != 0) {
                    int op = (~status) & limit;
                    dfs4(dp[status], op, 0, small - 1, cur);
                }
            }
            for (int i = 0; i < sn; i++) {
                dp[i] = 0;
            }
            int[] tmp = dp;
            dp = cur;
            cur = tmp;
        }
        return dp[limit];
    }

    public static void dfs4(int way, int op, int index, int end, int[] cur) {
        if (index == end) {
            cur[op] += way;
        } else {
            dfs4(way, op, index + 1, end, cur);
            if (((3 << index) & op) == 0) { // 11 << index 可以放砖
                dfs4(way, op | (3 << index), index + 1, end, cur);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(way(10, 6));
        System.out.println(ways4(10, 6));
    }





}
